import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-10-25
 * Time: 22:36
 */
public class Solution {
    public int FirstNotRepeatingChar (String str) {
        // write code here
        int len = str.length();
        Map<Character, Integer> map = new HashMap<>(); // 记录每个字符出现的位置, -1 表示不只出现 1 次
        Queue<Character> q1 = new LinkedList<>(); // 记录字符
        Queue<Integer> q2 = new LinkedList<>(); // 记录字符对应的下标
        for (int i = 0; i < len; i++) {
            char c = str.charAt(i);
            if (!map.containsKey(c)) {
                // 字符第一次出现
                q1.offer(c);
                q2.offer(i);
                map.put(c, i);
            } else {
                // 该字符出现过
                map.put(c, -1); // 用 -1 来表示出现不只一次
                while (!q1.isEmpty() && map.get(q1.peek()) == -1) {
                    // 队头要一直保证是只出现一次的元素
                    // 出现过
                    q1.poll();
                    q2.poll();
                }
            }
        }
        return q2.isEmpty() ? -1 : q2.poll();
    }
}
